package exer3;

import java.util.Stack;

class Solution {
    public static void main(String[] args) {
        int[]inOrder={9,3,15,20,7};
        int[]postOrder={9,15,7,20,3};
        Solution solution = new Solution();
        solution.buildTree(inOrder,postOrder);
    }
    private int postIndex=0;//创建后续遍历的指针
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        postIndex=postorder.length-1;
       return buildChild(inorder,postorder,0,inorder.length-1);

    }
    //寻找方法
    public int find(int[]inorder ,int val){
        for(int i=0;i<inorder.length;++i){
            if(inorder[i]==val){
                return i;
            }
        }
        return -1;
    }
    //创建子树
    public TreeNode buildChild(int[] inorder, int[] postorder,int begin,int end){
        // 检查是否后序和中序遍历数组是否完全相同，以及下标是否越界
        if(postIndex<0||begin>end){
            return null;
        }
        int val=postorder[postIndex];
        int index=find(inorder,val);
        if(index==-1){
            return null;
        }
        //创建结点
        Stack<Integer>stack=new Stack<>();
        stack.push(1);
        stack.pop();
        TreeNode root=new TreeNode(val);
        postIndex--;
        root.right=buildChild(inorder,postorder,index+1,end);
        root.left=buildChild(inorder,postorder,begin,index-1);

        return root;
    }
}